package primary.primary0;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class S0445两数相加II {


    class Solution {
        /**
         * 26, 栈
         * 这种涉及反过来的，想用递归做会很麻烦，用栈试一下
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Stack<ListNode> stack1 = new Stack<>();
            Stack<ListNode> stack2 = new Stack<>();
            ListNode temp1 = l1;
            ListNode temp2 = l2;
            while(temp1 != null){
                stack1.push(temp1);
                temp1 = temp1.next;
            }
            while(temp2 != null){
                stack2.push(temp2);
                temp2 = temp2.next;
            }
            int carry = 0;
            ListNode curNode = null;
            ListNode preNode = null;
            // 没有元素的话peek会报错，所以一定要用isEmpty
            while(!stack1.isEmpty() || !stack2.isEmpty()){
                // 这里的处理方式比先每个栈都取值，然后剩下来一个有值的栈一个空栈，再单独处理空栈好一些，简单不少
                int val1 = stack1.isEmpty()? 0: stack1.pop().val;
                int val2 = stack2.isEmpty()? 0: stack2.pop().val;
                int curAddRes = val1 + val2 + carry;
                curNode = new ListNode(curAddRes % 10);
                carry = curAddRes / 10;
                curNode.next = preNode;
                preNode = curNode;
            }
            // 最后保留了一个进位
            if(carry != 0){
                curNode = new ListNode(carry);
                curNode.next = preNode;
            }
            return curNode;
        }
    }

    /**
     * carry也放在判断里，比上面更好
     */
    class Solution2 {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Deque<Integer> stack1 = new ArrayDeque<Integer>();
            Deque<Integer> stack2 = new ArrayDeque<Integer>();
            while (l1 != null) {
                stack1.push(l1.val);
                l1 = l1.next;
            }
            while (l2 != null) {
                stack2.push(l2.val);
                l2 = l2.next;
            }
            int carry = 0;
            ListNode ans = null;
            while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
                int a = stack1.isEmpty() ? 0 : stack1.pop();
                int b = stack2.isEmpty() ? 0 : stack2.pop();
                int cur = a + b + carry;
                carry = cur / 10;
                cur %= 10;
                ListNode curnode = new ListNode(cur);
                curnode.next = ans;
                ans = curnode;
            }
            return ans;
        }
    }

    /**
     * 答案，递归写法
     * 不过是，先反转，再递归相加，再把相加的结果反转
     * 如果要求不使用其他数据结构，就只能这么写
     * 注意一下链表反转的代码吧
     */
    class Solution3 {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            l1 = reverseList(l1);
            l2 = reverseList(l2); // l1 和 l2 反转后，就变成【2. 两数相加】了
            ListNode l3 = addTwo(l1, l2, 0);
            return reverseList(l3);
        }

        private ListNode reverseList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            // mark: 这里的逻辑值得一看，reverseList是把当前节点后面的节点反转，反转后当前节点是尾巴，当前节点的next是null，然后返回新list的head
            ListNode newHead = reverseList(head.next);
            // 这里把自己添加到新list的tail后面，head.next是哪个节点没有被上面那行reverseList改变，他的next是空的，
            head.next.next = head;
            head.next = null; // 断开指向下一个节点的连接，保证最终链表的末尾节点的 next 是空节点
            return newHead;
        }

        // l1 和 l2 为当前遍历的节点，carry 为进位
        private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
            if (l1 == null && l2 == null) // 递归边界：l1 和 l2 都是空节点
                return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点
            if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
                l1 = l2;
                l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码
            }
            carry += l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起
            l1.val = carry % 10; // 每个节点保存一个数位
            l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), carry / 10); // 进位
            return l1;
        }
    }


    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        System.out.println(stack.peek());
    }
}
